// SPDX-License-Identifier: Apache-2.0
import { EPS } from "./api.js";

/**
 * Recursively evaluates function `fn` for `res` uniformly spaced values `t` in
 * the closed parametric interval `[start,end]` and computes corresponding
 * sample values `p`. For each `p` then calls `error` function to compute the
 * error to query target value `q` and eventually returns the `t` producing the
 * overall minimum error. At each level of recursion the search interval is
 * increasingly narrowed / centered around the best `t` of the current
 * iteration.
 *
 * The search is terminated early if the best error value is less than `eps`.
 *
 * The interval end points `start` and `end` MUST be normalized values in the
 * closed `[0,1]` interval.
 *
 * @param fn - function to evaluate
 * @param error - error function
 * @param q - target value
 * @param res - number of samples per interval
 * @param iter - max number of iterations / recursion limit
 * @param start - interval start
 * @param end - interval end
 */
export const minError = <T>(
	fn: (x: number) => T,
	error: (p: T, q: T) => number,
	q: T,
	res = 16,
	iter = 8,
	start = 0,
	end = 1,
	eps = EPS
): number => {
	if (iter <= 0) return (start + end) / 2;
	const delta = (end - start) / res;
	let minT = start;
	let minE = Infinity;
	for (let i = 0; i <= res; i++) {
		const t = start + i * delta;
		const e = error(q, fn(t));
		if (e < minE) {
			if (e <= eps) return t;
			minE = e;
			minT = t;
		}
	}
	return minError(
		fn,
		error,
		q,
		res,
		iter - 1,
		Math.max(minT - delta, 0),
		Math.min(minT + delta, 1)
	);
};
